package com.lijing.jumpGame;

/**
 * @Description TODO
 * @title: JumpGame01
 * @Author LiJing
 * @Date: 2021/4/610:57 上午
 * @Version 1.0
 */
public class JumpGame01 {
    public static void main(String[] args) {
        int[] a = {3,2,1,0,4};
        System.out.println(jump(a));
    }

    public static boolean jump(int[] stone){
        /*
         * @Date: 2021/4/6 10:58 上午
         * Step 1: 确定状态初始化
         * lastStep[i]表示跳到第i个石头最多还剩几步可以跳
         */
        int len = stone.length;
        int[] lastStep = new int[len];
        /*
         * @Date: 2021/4/6 11:01 上午
         * Step 2: 状态转移方程计算
         */
        lastStep[0] = stone[0];
        for (int i = 1; i < len; i++) {
            lastStep[i] = Math.max(lastStep[i-1]-1, stone[i]);
            if (i < len-1 && lastStep[i] == 0){
                return false;
            }
        }
        return true;
    }
}
